package com.mj.listen2._02_并查集;

/**
 * Quick Union - 基于rank的优化
 */
public class UnionFind_QU_R extends UnionFind_QU {

    /**
     * 用于保存每个根节点下面树的高度
     */
    private int[] ranks;

    public UnionFind_QU_R(int capacity) {
        super(capacity);
        // 默认初始化的时候每个节点的高度都是 1
        ranks = new int[capacity];
        for (int i = 0; i < ranks.length; i++) {
            // 以i为根节点的那颗树高度是 1
            ranks[i] = 1;
        }
    }

    @Override
    public void union(int v1, int v2) {
        // 找到 v1 所在的父节点
        int p1 = find(v1);
        int p2 = find(v2);

        if (p1 == p2) {
            // 本身v1和v2就是同一个集合
            return;
        }

        if (ranks[p1] < ranks[p2]) {
            // p1根节点子树高度小于p2根节点子树的高度。让p1根节点改为p2
            parents[p1] = p2;
        } else if (ranks[p1] > ranks[p2]) {
            // p2根节点子树高度小于p1根节点子树的高度。让p2根节点改为p1
            parents[p2] = p1;
        } else {
            // 相同的话，谁改为谁都可以
            parents[p1] = p2;
            // p2为根节点的那颗树高度增加1
            ranks[p2]++;
        }
    }
}
